// https://www.lintcode.com/problem/kth-smallest-number-in-sorted-matrix/description

// 描述
// 在一个排序矩阵中找从小到大的第 k 个整数。

// 排序矩阵的定义为：每一行递增，每一列也递增。

// 样例
// 给出 k = 4 和一个排序矩阵：

// [
  // [1 ,5 ,7],
  // [3 ,7 ,8],
  // [4 ,8 ,9],
// ]
// 返回 5。

// 挑战
// 使用O(k log n)的方法，n为矩阵的宽度和高度中的最大值。


// 没有用到排序矩阵的特征，直接当成数组做了。

class Solution {
public:
    /**
     * @param matrix: a matrix of integers
     * @param k: An integer
     * @return: the kth smallest number in the matrix
     */
     
    // 法一：堆
    // void heapify(vector<int>&nums, int n)
    // {
    //     while (n != 0)
    //     {
    //         int parent = (n - 1) / 2;
    //         if (nums[parent] < nums[n])
    //         {
    //             break;
    //         }
    //         swap(nums[parent], nums[n]);
    //         n = parent;
    //     }
    // }  
    
    // void heap_del(vector<int>&nums)
    // {
    //     nums[0] = nums.back();
    //     nums.pop_back();
    //     for (int i = 0; i < nums.size(); i++)
    //     {
    //         heapify(nums, i);
    //     }
    // }
    
    // int kthSmallest(vector<vector<int>> &matrix, int k) {
    //     vector<int> nums;
    //     for (int i = 0 ; i < matrix.size(); i++)
    //     {
    //         for (int j = 0; j < matrix[0].size(); j++)
    //         {
    //             nums.push_back(matrix[i][j]);
    //             heapify(nums, nums.size() - 1);
    //         }
    //     }
    //     while (--k)
    //     {
    //         heap_del(nums);
    //     }
    //     return nums[0];
    // }
  
    // 法二：multiset/priority_queue
    // int kthSmallest(vector<vector<int>> &matrix, int k) {
    //     multiset<int> nums;
    //     for (int i = 0; i < matrix.size(); i++)
    //     {
    //         for (int j = 0; j < matrix[0].size(); j++)
    //         {
    //             nums.insert(matrix[i][j]);
    //         }
    //     }
    //     multiset<int>::iterator it = nums.begin();
    //     while (--k)
    //     {
    //         ++it;
    //     }
    //     return *it;
    // }
    
    int kthSmallest(vector<vector<int>> &matrix, int k) {
        priority_queue<int, vector<int>, greater<int> > nums;
        for (int i = 0; i < matrix.size(); i++)
        {
            for (int j = 0; j < matrix[0].size(); j++)
            {
                nums.push(matrix[i][j]);
            }
        }
        while (--k)
        {
            nums.pop();
        }
        return nums.top();
    }
};